package leetcode.primary;

public class T115 {
    int len_s;
    int len_t;
    int num=0;
    public int numDistinct(String s, String t) {
        len_s = s.length();
        len_t = t.length();

        dfs(s,t,0,0);

        return num;
    }
    void dfs(String s,String t, int i,int j){

        if(len_t-i>len_s-j || j>=len_s || i>=len_t){
            return;
        }

        while(len_s-j>=len_t-i && j<len_s && i<len_t){
            System.out.println("t."+i+"="+t.charAt(i)+"  s."+j+"="+s.charAt(j));
            if(t.charAt(i)==s.charAt(j)){
                System.out.println("match rightly");
                if(i==len_t-1){
                    num++;
                    System.out.println(num);
                }
                dfs(s,t,i+1,j+1);
            }
            j++;
        }

    }

    public static void main( String[] args){
        String s = "babgbag";
        String t = "bag";
        T115 cc = new T115();
        int ans = cc.numDistinct(s,t);
        System.out.println(ans);
    }
}
